#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

const int N = 15;

int nums[N];
int group[N][N];
bool st[N];
int n;
int ans = N;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(int u, int gc, int x)
{
    for (int i = 0; i < gc; i++)
        if (gcd(nums[group[u][i]], nums[x]) > 1)
            return false;
    return true;
}

void dfs(int u, int gc, int tc, int start)
{
    if (u > ans) return;
    if (tc == n)
    {
        ans = min(ans, u);
        return;
    }

    bool flag = true;
    for (int i = start; i < n; i++)
    {
        if (!st[i] && check(u, gc, i))
        {
            st[i] = true;
            group[u][gc] = i;
            dfs(u, gc + 1, tc + 1, i + 1);
            st[i] = false;
            flag = false;
        }
    }

    if (flag)    dfs(u + 1, 0, tc, 0);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)    cin >> nums[i];

    dfs(1, 0, 0, 0);
    cout << ans << endl;
    return 0;
}